//把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。 
//
// 
//
// 你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。 
//
// 
//
// 示例 1: 
//
// 输入: 1
//输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]
// 
//
// 示例 2: 
//
// 输入: 2
//输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0
//.05556,0.02778] 
//
// 
//
// 限制： 
//
// 1 <= n <= 11 
// Related Topics 数学 动态规划 概率与统计 👍 354 👎 0

package com.cute.leetcode.editor.cn;

import java.util.Arrays;

public class NgeTouZiDeDianShuLcof {
    public static void main(String[] args) {
        Solution solution = new NgeTouZiDeDianShuLcof().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 使用动态规划进行正向递推：即从f(n-1) -> f(n)
         * 使用dp保存和出现的概率值
         */
        public double[] dicesProbability(int n) {
            double[] dp = new double[6];
            Arrays.fill(dp, 1.0 / 6.0); //初始化1个骰子时的概率
            for (int i = 2; i <= n ; i++) {// 遍历所有的骰子
                double[] temp = new double[5 * i + 1];// 保存共i个骰子时所有的和的数量
                //注意下标并不代表实际值，0只是能代表当前骰子能取到的最小和而已
                for (int j = 0; j < dp.length; j++) {// 遍历i-1个骰子能取到的所有的和的概率
                    for (int k = 0; k < 6; k++) {// 新的骰子只有6种选择，所以从f(n-1)->f(n)时 n-1中的结果会对n中造成六次影响
                        temp[j + k] += dp[j] / 6.0;// j+k是不会发生越界的
                    }
                }
                dp = temp;//更新骰子为当前骰子
            }
            return dp;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}